home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / oper_sys / emerald / emrldsys.lha / Language / Compiler / ndbm.c < prev    next >
C/C++ Source or Header  |  1990-08-16  |  11KB  |  532 lines
  1. /* 
  2.  * @(#)ndbm.c    1.1  6/10/87
  3.  */
  4. /*
  5.  * Copyright (c) 1983 Regents of the University of California.
  6.  * All rights reserved.  The Berkeley software License Agreement
  7.  * specifies the terms and conditions for redistribution.
  8.  */
  9.  
  10. #if defined(LIBC_SCCS) && !defined(lint)
  11. static char sccsid[] = "@(#)ndbm.c    5.3 (Berkeley) 3/9/86";
  12. #endif LIBC_SCCS and not lint
  13.  
  14. #include <sys/types.h>
  15. #include <sys/stat.h>
  16. #include <sys/file.h>
  17. #include <stdio.h>
  18. #include <errno.h>
  19. #include "ndbm.h"
  20.  
  21. #define BYTESIZ 8
  22. #undef setbit
  23.  
  24. static  datum makdatum();
  25. static  long hashinc();
  26. static  long dcalchash();
  27. extern  int errno;
  28.  
  29. DBM *
  30. dbm_open(file, flags, mode)
  31.     char *file;
  32.     int flags, mode;
  33. {
  34.     struct stat statb;
  35.     register DBM *db;
  36.  
  37.     if ((db = (DBM *)malloc(sizeof *db)) == 0) {
  38.         errno = ENOMEM;
  39.         return ((DBM *)0);
  40.     }
  41.     db->dbm_flags = (flags & 03) == O_RDONLY ? _DBM_RDONLY : 0;
  42.     if ((flags & 03) == O_WRONLY)
  43.         flags = (flags & ~03) | O_RDWR;
  44.     strcpy(db->dbm_pagbuf, file);
  45.     strcat(db->dbm_pagbuf, ".pag");
  46.     db->dbm_pagf = open(db->dbm_pagbuf, flags, mode);
  47.     if (db->dbm_pagf < 0)
  48.         goto bad;
  49.     strcpy(db->dbm_pagbuf, file);
  50.     strcat(db->dbm_pagbuf, ".dir");
  51.     db->dbm_dirf = open(db->dbm_pagbuf, flags, mode);
  52.     if (db->dbm_dirf < 0)
  53.         goto bad1;
  54.     fstat(db->dbm_dirf, &statb);
  55.     db->dbm_maxbno = statb.st_size*BYTESIZ-1;
  56.     db->dbm_pagbno = db->dbm_dirbno = -1;
  57.     return (db);
  58. bad1:
  59.     (void) close(db->dbm_pagf);
  60. bad:
  61.     free((char *)db);
  62.     return ((DBM *)0);
  63. }
  64.  
  65. void
  66. dbm_close(db)
  67.     DBM *db;
  68. {
  69.  
  70.     (void) close(db->dbm_dirf);
  71.     (void) close(db->dbm_pagf);
  72.     free((char *)db);
  73. }
  74.  
  75. long
  76. dbm_forder(db, key)
  77.     register DBM *db;
  78.     datum key;
  79. {
  80.     long hash;
  81.  
  82.     hash = dcalchash(key);
  83.     for (db->dbm_hmask=0;; db->dbm_hmask=(db->dbm_hmask<<1)+1) {
  84.         db->dbm_blkno = hash & db->dbm_hmask;
  85.         db->dbm_bitno = db->dbm_blkno + db->dbm_hmask;
  86.         if (getbit(db) == 0)
  87.             break;
  88.     }
  89.     return (db->dbm_blkno);
  90. }
  91.  
  92. datum
  93. dbm_fetch(db, key)
  94.     register DBM *db;
  95.     datum key;
  96. {
  97.     register i;
  98.     datum item;
  99.  
  100.     if (dbm_error(db))
  101.         goto err;
  102.     dbm_access(db, dcalchash(key));
  103.     if ((i = finddatum(db->dbm_pagbuf, key)) >= 0) {
  104.         item = makdatum(db->dbm_pagbuf, i+1);
  105.         if (item.dptr != NULL)
  106.             return (item);
  107.     }
  108. err:
  109.     item.dptr = NULL;
  110.     item.dsize = 0;
  111.     return (item);
  112. }
  113.  
  114. dbm_delete(db, key)
  115.     register DBM *db;
  116.     datum key;
  117. {
  118.     register i;
  119.     datum item;
  120.  
  121.     if (dbm_error(db))
  122.         return (-1);
  123.     if (dbm_rdonly(db)) {
  124.         errno = EPERM;
  125.         return (-1);
  126.     }
  127.     dbm_access(db, dcalchash(key));
  128.     if ((i = finddatum(db->dbm_pagbuf, key)) < 0)
  129.         return (-1);
  130.     if (!delitem(db->dbm_pagbuf, i))
  131.         goto err;
  132.     db->dbm_pagbno = db->dbm_blkno;
  133.     (void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET);
  134.     if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) {
  135.     err:
  136.         db->dbm_flags |= _DBM_IOERR;
  137.         return (-1);
  138.     }
  139.     return (0);
  140. }
  141.  
  142. dbm_store(db, key, dat, replace)
  143.     register DBM *db;
  144.     datum key, dat;
  145.     int replace;
  146. {
  147.     register i;
  148.     datum item, item1;
  149.     char ovfbuf[PBLKSIZ];
  150.  
  151.     if (dbm_error(db))
  152.         return (-1);
  153.     if (dbm_rdonly(db)) {
  154.         errno = EPERM;
  155.         return (-1);
  156.     }
  157. loop:
  158.     dbm_access(db, dcalchash(key));
  159.     if ((i = finddatum(db->dbm_pagbuf, key)) >= 0) {
  160.         if (!replace)
  161.             return (1);
  162.         if (!delitem(db->dbm_pagbuf, i)) {
  163.             db->dbm_flags |= _DBM_IOERR;
  164.             return (-1);
  165.         }
  166.     }
  167.     if (!additem(db->dbm_pagbuf, key, dat))
  168.         goto split;
  169.     db->dbm_pagbno = db->dbm_blkno;
  170.     (void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET);
  171.     if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) {
  172.         db->dbm_flags |= _DBM_IOERR;
  173.         return (-1);
  174.     }
  175.     return (0);
  176.  
  177. split:
  178.     if (key.dsize+dat.dsize+3*sizeof(short) >= PBLKSIZ) {
  179.         db->dbm_flags |= _DBM_IOERR;
  180.         errno = ENOSPC;
  181.         return (-1);
  182.     }
  183.     bzero(ovfbuf, PBLKSIZ);
  184.     for (i=0;;) {
  185.         item = makdatum(db->dbm_pagbuf, i);
  186.         if (item.dptr == NULL)
  187.             break;
  188.         if (dcalchash(item) & (db->dbm_hmask+1)) {
  189.             item1 = makdatum(db->dbm_pagbuf, i+1);
  190.             if (item1.dptr == NULL) {
  191.                 fprintf(stderr, "ndbm: split not paired\n");
  192.                 db->dbm_flags |= _DBM_IOERR;
  193.                 break;
  194.             }
  195.             if (!additem(ovfbuf, item, item1) ||
  196.                 !delitem(db->dbm_pagbuf, i)) {
  197.                 db->dbm_flags |= _DBM_IOERR;
  198.                 return (-1);
  199.             }
  200.             continue;
  201.         }
  202.         i += 2;
  203.     }
  204.     db->dbm_pagbno = db->dbm_blkno;
  205.     (void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET);
  206.     if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) {
  207.         db->dbm_flags |= _DBM_IOERR;
  208.         return (-1);
  209.     }
  210.     (void) lseek(db->dbm_pagf, (db->dbm_blkno+db->dbm_hmask+1)*PBLKSIZ, L_SET);
  211.     if (write(db->dbm_pagf, ovfbuf, PBLKSIZ) != PBLKSIZ) {
  212.         db->dbm_flags |= _DBM_IOERR;
  213.         return (-1);
  214.     }
  215.     setbit(db);
  216.     goto loop;
  217. }
  218.  
  219. datum
  220. dbm_firstkey(db)
  221.     DBM *db;
  222. {
  223.  
  224.     db->dbm_blkptr = 0L;
  225.     db->dbm_keyptr = 0;
  226.     return (dbm_nextkey(db));
  227. }
  228.  
  229. datum
  230. dbm_nextkey(db)
  231.     register DBM *db;
  232. {
  233.     struct stat statb;
  234.     datum item;
  235.  
  236.     if (dbm_error(db) || fstat(db->dbm_pagf, &statb) < 0)
  237.         goto err;
  238.     statb.st_size /= PBLKSIZ;
  239.     for (;;) {
  240.         if (db->dbm_blkptr != db->dbm_pagbno) {
  241.             db->dbm_pagbno = db->dbm_blkptr;
  242.             (void) lseek(db->dbm_pagf, db->dbm_blkptr*PBLKSIZ, L_SET);
  243.             if (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)
  244.                 bzero(db->dbm_pagbuf, PBLKSIZ);
  245. #ifdef DEBUG
  246.             else if (chkblk(db->dbm_pagbuf) < 0)
  247.                 db->dbm_flags |= _DBM_IOERR;
  248. #endif
  249.         }
  250.         if (((short *)db->dbm_pagbuf)[0] != 0) {
  251.             item = makdatum(db->dbm_pagbuf, db->dbm_keyptr);
  252.             if (item.dptr != NULL) {
  253.                 db->dbm_keyptr += 2;
  254.                 return (item);
  255.             }
  256.             db->dbm_keyptr = 0;
  257.         }
  258.         if (++db->dbm_blkptr >= statb.st_size)
  259.             break;
  260.     }
  261. err:
  262.     item.dptr = NULL;
  263.     item.dsize = 0;
  264.     return (item);
  265. }
  266.  
  267. static
  268. dbm_access(db, hash)
  269.     register DBM *db;
  270.     long hash;
  271. {
  272.  
  273.     for (db->dbm_hmask=0;; db->dbm_hmask=(db->dbm_hmask<<1)+1) {
  274.         db->dbm_blkno = hash & db->dbm_hmask;
  275.         db->dbm_bitno = db->dbm_blkno + db->dbm_hmask;
  276.         if (getbit(db) == 0)
  277.             break;
  278.     }
  279.     if (db->dbm_blkno != db->dbm_pagbno) {
  280.         db->dbm_pagbno = db->dbm_blkno;
  281.         (void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET);
  282.         if (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)
  283.             bzero(db->dbm_pagbuf, PBLKSIZ);
  284. #ifdef DEBUG
  285.         else if (chkblk(db->dbm_pagbuf) < 0)
  286.             db->dbm_flags |= _DBM_IOERR;
  287. #endif
  288.     }
  289. }
  290.  
  291. static
  292. getbit(db)
  293.     register DBM *db;
  294. {
  295.     long bn;
  296.     register b, i, n;
  297.     
  298.  
  299.     if (db->dbm_bitno > db->dbm_maxbno)
  300.         return (0);
  301.     n = db->dbm_bitno % BYTESIZ;
  302.     bn = db->dbm_bitno / BYTESIZ;
  303.     i = bn % DBLKSIZ;
  304.     b = bn / DBLKSIZ;
  305.     if (b != db->dbm_dirbno) {
  306.         db->dbm_dirbno = b;
  307.         (void) lseek(db->dbm_dirf, (long)b*DBLKSIZ, L_SET);
  308.         if (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)
  309.             bzero(db->dbm_dirbuf, DBLKSIZ);
  310.     }
  311.     return (db->dbm_dirbuf[i] & (1<<n));
  312. }
  313.  
  314. static
  315. setbit(db)
  316.     register DBM *db;
  317. {
  318.     long bn;
  319.     register i, n, b;
  320.  
  321.     if (db->dbm_bitno > db->dbm_maxbno)
  322.         db->dbm_maxbno = db->dbm_bitno;
  323.     n = db->dbm_bitno % BYTESIZ;
  324.     bn = db->dbm_bitno / BYTESIZ;
  325.     i = bn % DBLKSIZ;
  326.     b = bn / DBLKSIZ;
  327.     if (b != db->dbm_dirbno) {
  328.         db->dbm_dirbno = b;
  329.         (void) lseek(db->dbm_dirf, (long)b*DBLKSIZ, L_SET);
  330.         if (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)
  331.             bzero(db->dbm_dirbuf, DBLKSIZ);
  332.     }
  333.     db->dbm_dirbuf[i] |= 1<<n;
  334.     db->dbm_dirbno = b;
  335.     (void) lseek(db->dbm_dirf, (long)b*DBLKSIZ, L_SET);
  336.     if (write(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)
  337.         db->dbm_flags |= _DBM_IOERR;
  338. }
  339.  
  340. static datum
  341. makdatum(buf, n)
  342.     char buf[PBLKSIZ];
  343. {
  344.     register short *sp;
  345.     register t;
  346.     datum item;
  347.  
  348.     sp = (short *)buf;
  349.     if ((unsigned)n >= sp[0]) {
  350.         item.dptr = NULL;
  351.         item.dsize = 0;
  352.         return (item);
  353.     }
  354.     t = PBLKSIZ;
  355.     if (n > 0)
  356.         t = sp[n];
  357.     item.dptr = buf+sp[n+1];
  358.     item.dsize = t - sp[n+1];
  359.     return (item);
  360. }
  361.  
  362. static
  363. finddatum(buf, item)
  364.     char buf[PBLKSIZ];
  365.     datum item;
  366. {
  367.     register short *sp;
  368.     register int i, n, j;
  369.  
  370.     sp = (short *)buf;
  371.     n = PBLKSIZ;
  372.     for (i=0, j=sp[0]; i<j; i+=2, n = sp[i]) {
  373.         n -= sp[i+1];
  374.         if (n != item.dsize)
  375.             continue;
  376.         if (n == 0 || bcmp(&buf[sp[i+1]], item.dptr, n) == 0)
  377.             return (i);
  378.     }
  379.     return (-1);
  380. }
  381.  
  382. static  int hitab[16]
  383. /* ken's
  384. {
  385.     055,043,036,054,063,014,004,005,
  386.     010,064,077,000,035,027,025,071,
  387. };
  388. */
  389.  = {    61, 57, 53, 49, 45, 41, 37, 33,
  390.     29, 25, 21, 17, 13,  9,  5,  1,
  391. };
  392. static  long hltab[64]
  393.  = {
  394.     06100151277L,06106161736L,06452611562L,05001724107L,
  395.     02614772546L,04120731531L,04665262210L,07347467531L,
  396.     06735253126L,06042345173L,03072226605L,01464164730L,
  397.     03247435524L,07652510057L,01546775256L,05714532133L,
  398.     06173260402L,07517101630L,02431460343L,01743245566L,
  399.     00261675137L,02433103631L,03421772437L,04447707466L,
  400.     04435620103L,03757017115L,03641531772L,06767633246L,
  401.     02673230344L,00260612216L,04133454451L,00615531516L,
  402.     06137717526L,02574116560L,02304023373L,07061702261L,
  403.     05153031405L,05322056705L,07401116734L,06552375715L,
  404.     06165233473L,05311063631L,01212221723L,01052267235L,
  405.     06000615237L,01075222665L,06330216006L,04402355630L,
  406.     01451177262L,02000133436L,06025467062L,07121076461L,
  407.     03123433522L,01010635225L,01716177066L,05161746527L,
  408.     01736635071L,06243505026L,03637211610L,01756474365L,
  409.     04723077174L,03642763134L,05750130273L,03655541561L,
  410. };
  411.  
  412. static long
  413. hashinc(db, hash)
  414.     register DBM *db;
  415.     long hash;
  416. {
  417.     long bit;
  418.  
  419.     hash &= db->dbm_hmask;
  420.     bit = db->dbm_hmask+1;
  421.     for (;;) {
  422.         bit >>= 1;
  423.         if (bit == 0)
  424.             return (0L);
  425.         if ((hash & bit) == 0)
  426.             return (hash | bit);
  427.         hash &= ~bit;
  428.     }
  429. }
  430.  
  431. static long
  432. dcalchash(item)
  433.     datum item;
  434. {
  435.     register int s, c, j;
  436.     register char *cp;
  437.     register long hashl;
  438.     register int hashi;
  439.  
  440.     hashl = 0;
  441.     hashi = 0;
  442.     for (cp = item.dptr, s=item.dsize; --s >= 0; ) {
  443.         c = *cp++;
  444.         for (j=0; j<BYTESIZ; j+=4) {
  445.             hashi += hitab[c&017];
  446.             hashl += hltab[hashi&63];
  447.             c >>= 4;
  448.         }
  449.     }
  450.     return (hashl);
  451. }
  452.  
  453. /*
  454.  * Delete pairs of items (n & n+1).
  455.  */
  456. static
  457. delitem(buf, n)
  458.     char buf[PBLKSIZ];
  459. {
  460.     register short *sp, *sp1;
  461.     register i1, i2;
  462.  
  463.     sp = (short *)buf;
  464.     i2 = sp[0];
  465.     if ((unsigned)n >= i2 || (n & 1))
  466.         return (0);
  467.     if (n == i2-2) {
  468.         sp[0] -= 2;
  469.         return (1);
  470.     }
  471.     i1 = PBLKSIZ;
  472.     if (n > 0)
  473.         i1 = sp[n];
  474.     i1 -= sp[n+2];
  475.     if (i1 > 0) {
  476.         i2 = sp[i2];
  477.         bcopy(&buf[i2], &buf[i2 + i1], sp[n+2] - i2);
  478.     }
  479.     sp[0] -= 2;
  480.     for (sp1 = sp + sp[0], sp += n+1; sp <= sp1; sp++)
  481.         sp[0] = sp[2] + i1;
  482.     return (1);
  483. }
  484.  
  485. /*
  486.  * Add pairs of items (item & item1).
  487.  */
  488. static
  489. additem(buf, item, item1)
  490.     char buf[PBLKSIZ];
  491.     datum item, item1;
  492. {
  493.     register short *sp;
  494.     register i1, i2;
  495.  
  496.     sp = (short *)buf;
  497.     i1 = PBLKSIZ;
  498.     i2 = sp[0];
  499.     if (i2 > 0)
  500.         i1 = sp[i2];
  501.     i1 -= item.dsize + item1.dsize;
  502.     if (i1 <= (i2+3) * sizeof(short))
  503.         return (0);
  504.     sp[0] += 2;
  505.     sp[++i2] = i1 + item1.dsize;
  506.     bcopy(item.dptr, &buf[i1 + item1.dsize], item.dsize);
  507.     sp[++i2] = i1;
  508.     bcopy(item1.dptr, &buf[i1], item1.dsize);
  509.     return (1);
  510. }
  511.  
  512. #ifdef DEBUG
  513. static
  514. chkblk(buf)
  515.     char buf[PBLKSIZ];
  516. {
  517.     register short *sp;
  518.     register t, i;
  519.  
  520.     sp = (short *)buf;
  521.     t = PBLKSIZ;
  522.     for (i=0; i<sp[0]; i++) {
  523.         if (sp[i+1] > t)
  524.             return (-1);
  525.         t = sp[i+1];
  526.     }
  527.     if (t < (sp[0]+1)*sizeof(short))
  528.         return (-1);
  529.     return (0);
  530. }
  531. #endif
  532.